package com.zwd.cases.algorithm;

import java.util.Arrays;

/**
 * @Description 插入排序
 * @Author zhengwd
 * @Date 2022/8/1 14:51
 **/
public class InsertSort {

    public static void main(String[] args) {
        // 测试数据
        int[] array = {19, 15, 37, 12, 25};
        // 19, 15, 37, 12, 25   =》  15, 19, 37, 12, 25  =》  15, 19, 37, 12, 25  =》  12, 15, 19, 37, 25 =》  12, 15, 19, 25 37


        // 插入排序
//        insertSort(array);
        insertSort2(array);
        // 遍历输出
        Arrays.stream(array).forEach(System.out::println);
    }

    private static void insertSort2(int[] array) {
        int len = array.length;
        // 从第二个数据开始处理
        for (int i = 1; i < len; i++) {
            // 当当前数据小于上一个数据时才进去数据处理
            if (array[i] < array[i - 1]) {
                int temp = array[i];
                // 从当前数据开始处理
                int j = i;
                while (j > 0 && temp < array[j - 1]) {
                    array[j] = array[j - 1];
                    j--;
                }
                array[j] = temp;
            }
        }

    }

    /**
     * 插入排序
     * @param array 集合
     */
    private static void insertSort(int[] array) {
        // 判空
        if (array == null || array.length == 0) {
            return;
        }
        // 数据处理
        int length = array.length;
        for (int i = 1; i < length; i++) {
            // 当 array[i] 比 array[i - 1] 小时才进入处理
            if (array[i] < array[i - 1]) {
                // 临时变量存储array[i]的值
                int temp = array[i];
                // 从当前位置开始处理
                int j = i;
                // 将比temp大的数往后挪一个位置，为temp腾出一个合适的位置
                while (j > 0 && temp < array[j - 1]) {
                    array[j] = array[j - 1];
                    // 填充完后，继续向前比较
                    j--;
                }
                // 将temp放在属于它的位置上
                array[j] = temp;
            }
        }
    }
}
